#include<vector>
#include<iostream>
using namespace std;

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int a = 0, b = 0;

        int m = matrix.size();
        int n = matrix[0].size();
        vector<vector<bool>> check(m, vector<bool>(n, false));
            while (a < m && b < n)
        {
            int x = matrix[a][b];
            check[a][b] = true;
            if (x < target)
            {
                if (a + 1 < m && check[a + 1][b] == false)
                {
                    a++;
                }
                else if (b + 1 < n && check[a][b + 1] == false)
                {
                    b++;
                }
            }
            else if (x > target)
            {
                if (a - 1 >= 0 && check[a - 1][b] == true)
                {
                    a--;
                }
                else if (b - 1 >= 0 && check[a][b - 1] == true)
                {
                    b--;
                }
            }
            else
            {
                return true;
            }
        }
        return false;
    }
};

int main()
{
    vector<vector<int>> nums = { {1, 4, 7, 11, 15},{2, 5, 8, 12, 19},{3, 6, 9, 16, 22},{10, 13, 14, 17, 24},{18, 21, 23, 26, 30} };
    Solution s;
    s.searchMatrix(nums, 5);
    return 0;
}